--[[
	哈希表
	哈希表中的key就是通过函数转换为一个整数
	哈希函数会有冲突 f(key1) = f(key2) , key1 ~= key2, 哈希表会用链表法解决这个问题

	node = {
		key,
		value,
	}
--]]
local string = string
local string_len = string.len
local string_byte = string.byte
local math = math


local Hashmap = {}

function Hashmap.new(...)
	local instance = setmetatable({}, {__index=Hashmap})
	instance:ctor(...)
	return instance
end

function Hashmap:ctor(func)
	self.nodes = {} --列表
	self.count = 0 --元素个数
	self.key_func = func
end
function Hashmap:hashKey(key)
	if not self.key_func then
		return key
	end
	local h = self.key_func(key)
	print("h:", h)
	return h
end

function Hashmap:set(key, value)
	local h = self:hashKey(key)
	local x = self.nodes[h]
	local found = false
	if x then
		--不同的key可能产生的hask key 一样，用链表法解决这个问题
		while x ~= nil do
			if x.key == key then
				found = true
				x.value = value
				break
			end
			x = x.next
		end
		if found == false then
			local old = self.nodes[h]
			self.nodes[h] = {
				key = key,
				value = value,
				next = old,
			}
			self.count = self.count + 1
		end
	else
		self.nodes[h] = {
			key = key,
			value = value,
		}
	end
end

function Hashmap:get(key)
	local h = self:hashKey(key)
	local node = self.nodes[h]
	if node then
		return node.value
	end
	return
end

function Hashmap:remove(key)
	local h = self:hashKey(key)
	local node = self.nodes[h]
	if node then
		if node.next then
			self.nodes[h] = node.next
		else
			self.nodes[h] = nil
		end
		self.count = self.count - 1
	end
end

function Hashmap:empty()
	if self.count > 0 then
		return false
	end
	return true
end

function Hashmap:print()
	for k, v in pairs(self.nodes) do
		print(v.key, v.value)
		local n = v.next
		while n do
			print(n.key, n.value)
			n = n.next
		end
	end
end

------------------------------------------------------------------
--测试
------------------------------------------------------------------
if arg and arg[0] == "hashmap.lua" then
	local crc = require("crc32")
	local hashmap = Hashmap.new(crc.hash)
	hashmap:set("sss", 1234)
	hashmap:set("12341", 1234)
	hashmap:set("122", 1234)
	hashmap:set("s", 12234234)
	hashmap:set("s1", 12234234)
	hashmap:set("s2", 12234234)

	hashmap:print()
	print("_______")

	hashmap:remove("122")
	hashmap:print()
	print("_______")
	print("get key :", hashmap:get("s"))
end



return Hashmap

